package algorithm.dp;

public class 最大加号标志 {
/*
 * 在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k" 阶由 1 组成的“轴对称”加号标志具有中心网格  grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

 

k 阶轴对称加号标志示例:

阶 1:
000
010
000

阶 2:
00000
00100
01110
00100
00000

阶 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
 

示例 1：

输入: N = 5, mines = [[4, 2]]
输出: 2
解释:

11111
11111
11111
11111
11011

在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-plus-sign
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

    public int orderOfLargestPlusSign(int N, int[][] mines) {
        /*
         * 如果dp[i][j] = n-1,并且map[i][j+n] map[i+n][j] map[i-n][j] map[i][j-n]
         * 均为1，那么dp[i][j] = n 最近提交结果： 通过 显示详情 执行用时 : 870 ms , 在所有Java提交中击败了
         * 6.15% 的用户 内存消耗 : 56.9 MB , 在所有Java提交中击败了 60.87% 的用户
         */
        boolean goOn = true;
        int[][] map = new int[N + 5][N + 5];
        int[][] dp = new int[N + 5][N + 5];
        // 地图障碍初始化 和题目中反过来，1是障碍，0是阶
        for (int[] mine : mines) {
            int i = mine[0];
            int j = mine[1];
            map[i][j] = 1;
            dp[i][j] = -1;
        }
        for (int k = 1; k < N; k++) {
            goOn = false;
            for (int i = k - 1; i <= N - k; i++) {
                for (int j = k - 1; j <= N - k; j++) {
                    if (dp[i][j] < 0) {
                        continue;
                    }
                    if (map[i][j - k + 1] == 1 || map[i - k + 1][j] == 1 || map[i + k - 1][j] == 1
                            || map[i][j + k - 1] == 1) {
                        dp[i][j] = -1;
                    } else {
                        goOn = true;
                    }
                }
            }
            if (!goOn) {
                return k - 1;
            }
        }
        return N;
    }

    public static void main(String[] args) {

        最大加号标志 run = new 最大加号标志();
        int[][] a = { { 4, 2 } };
        System.out.println(run.orderOfLargestPlusSign(5, a));
    }
}
